import heapq


class Solution:
    def mincostToHireWorkers(self, quality: list, wage: list, K: int) -> float:
        ratioAndQ = []
        for i in range(len(quality)):
            ratioAndQ.append((wage[i] / quality[i], quality[i]))
        ratioAndQ.sort()
        queue = []
        qsum = 0
        ans = 2**31
        for ratio, q in ratioAndQ:
            qsum += q
            heapq.heappush(queue, -q)
            if len(queue) > K:
                maxq = -heapq.heappop(queue)
                qsum -= maxq
            if len(queue) == K:
                ans = min(ans, qsum * ratio)

        return ans
